package day0318

var directions = [4][2]int{{0, -1}, {1, 0}, {-1, 0}, {0, 1}}

func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	used := make([][]bool, m)
	for i := 0; i < m; i++ {
		used[i] = make([]bool, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == word[0] {
				if dfs(board, word, i, j, 0, used) {
					return true
				}
			}
		}
	}
	return false
}

func dfs(board [][]byte, word string, i, j, index int, used [][]bool) bool {
	if index == len(word) {
		return true
	}
	if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) || board[i][j] != word[index] || used[i][j] {
		return false
	}
	used[i][j] = true
	for k := 0; k < 4; k++ {
		if dfs(board, word, i+directions[k][0], j+directions[k][1], index+1, used) {
			return true
		}
	}
	used[i][j] = false
	return false
}
